package tree;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;

public class ValidateBinarySearchTree98 {

    @Test
    public void test() {
        print(Arrays.asList(2,1,3));
        print(Arrays.asList(5,1,4,null,null,3,6));
    }

    void print(List<Integer> list) {
        TreeNode root = TreeNode.buildTree(list);
        boolean valid = isValidBST(root);
        System.out.format("tree: %s, valid: %s\n", list, valid);
    }

    public boolean isValidBST(TreeNode root) {
        return validate(root, null, null);
    }

    // 越往下递归, (min, max) 范围越缩小
    public boolean validate(TreeNode node, TreeNode min, TreeNode max) {
        if (node == null) {
            return true;
        }
        if (min != null && node.val <= min.val) {
            return false;
        }
        if (max != null && node.val >= max.val) {
            return false;
        }
        if (!validate(node.left, min, node)) {
            return false;
        }
        if (!validate(node.right, node, max)) {
            return false;
        }
        return true;
    }

    // 以下方法不对, 把 root/left/right/min/max 绕进去了.
    // 如果引入了min/max, 就应该只判断node本身. 对left/right的判断交给递归去做, 这里只负责更新min或max到下个递归
    public boolean validate0(TreeNode node, TreeNode min, TreeNode max) {
        if (node == null) {
            return true;
        }
        if (node.left != null) {
            if (max != null && node.left.val >= max.val) {
                return false;
            }
            if (min != null && node.left.val <= min.val) {
                return false;
            }
            if (!validate0(node.left, min, node)) {
                return false;
            }
        }

        if (node.right != null) {
            if (min != null && node.right.val <= min.val) {
                return false;
            }
            if (max != null && node.right.val >= max.val) {
                return false;
            }
            if (!validate0(node.right, node, max)) {
                return false;
            }
        }
        return true;
    }
}
